#include<bits/stdc++.h>
#define INF (1ll<<50)
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=41*41;
int n,m,head[MAXN],cnt,a[41][41],_x[]={0,0,1,-1},_y[]={1,-1,0,0};
LL _max,tot1,tot2,sum1,sum2;
struct edge
{
	int v,next;
	LL val;
}e[MAXN*10];
void addedge(int x,int y,LL z)
{
	e[cnt]=(edge){y,head[x],z};
	head[x]=cnt++;
	swap(x,y);
	e[cnt]=(edge){y,head[x],0};
	head[x]=cnt++;
	return;
}
struct MF
{
	int idx[MAXN],cur[MAXN],S,T;
	void bfs()
	{
		memset(idx,0,sizeof(idx));
		queue<int>q;
		q.push(S);
		idx[S]=1;
		while(!q.empty())
		{
			int u=q.front();q.pop();
			for(int i=head[u];~i;i=e[i].next)
			{
				int v=e[i].v;
				if(idx[v]||!e[i].val)continue;
				idx[v]=idx[u]+1;
				q.push(v);
			}
		}
		return;
	}
	LL dfs(int u,LL _min)
	{
		if(u==T)return _min;
		LL k,ret=0;
		for(int i=cur[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			cur[u]=i;
			if(idx[v]!=idx[u]+1||!e[i].val)continue;
			k=dfs(v,min(_min-ret,e[i].val));
			e[i].val-=k;
			e[i^1].val+=k;
			ret+=k;
			if(ret==_min)break;
		}
		return ret;
	}
	LL dinic()
	{
		LL ret=0;
		while(true)
		{
			bfs();
			if(!idx[T])break;
			memcpy(cur,head,sizeof(head));
			ret+=dfs(S,INF);
		}
		return ret;
	}
}T1;
inline int ID(int x,int y)
{
	return (x-1)*m+y;
}
bool chk(LL x)
{
	int S=0,T=n*m+1;
	memset(head,-1,sizeof(head));cnt=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if((i+j)&1)
			{
				addedge(S,ID(i,j),x-a[i][j]);
				for(int k=0;k<4;++k)
				{
					int xx=i+_x[k],yy=j+_y[k];
					if(!xx||!yy||xx>n||yy>m)continue;
					addedge(ID(i,j),ID(xx,yy),INF);
				}
			}
			else addedge(ID(i,j),T,x-a[i][j]);
	T1.S=S;T1.T=T;
	LL ans=T1.dinic();
	if(ans==x*tot1-sum1)return true;
	return false;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int T=read();
	while(T--)
	{
		n=read();m=read();
		_max=tot1=tot2=sum1=sum2=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
			{
				a[i][j]=read();
				_max=max(_max,(LL)a[i][j]);
				if((i+j)&1)++tot1,sum1+=a[i][j];
				else ++tot2,sum2+=a[i][j];
			}
		if(tot1!=tot2)
		{
			LL x=(sum1-sum2)/(tot1-tot2);
			if(x>=_max&&chk(x))printf("%lld\n",tot1*x-sum1);
			else puts("-1");
			continue;
		}
		else
		{
			if(sum1!=sum2)puts("-1");
			else
			{
				LL l=_max,r=INF;
				while(l<=r)
				{
					LL mid=(l+r)>>1;
					if(chk(mid))r=mid-1;
					else l=mid+1;
				}
				printf("%lld\n",tot1*l-sum1);
			}
		}
	}
	return 0;
}
